package _01_sort;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author: mornd
 * @dateTime: 2023/6/23 - 11:41
 * 桶排序
 * 它将待排序元素划分为一定数量的桶（buckets），然后将元素分配到不同的桶中，
 * 每个桶内部再使用其他排序算法或递归地使用桶排序进行排序。最后，将各个桶中的元素按顺序合并起来，即可得到有序序列。
 */
public class BucketSort {
    @Test
    public void test() {
//        int[] arr = {2, 10, 11, 32, 16, 6, 28, 18, 5, 12};
        int[] arr = {1,2,3,4,5,6,7,8,9};
        bucketSort(arr, 2);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr
     * @param bucketSize 每个桶存储最多元素个数
     */
    public void bucketSort(int[] arr, int bucketSize) {
        if (arr.length == 0) {
            return;
        }

        // 记录数组中的最大值和最小值
        int maxValue = arr[0];
        int minValue = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxValue) {
                maxValue = arr[i];
            }
            if (arr[i] < minValue) {
                minValue = arr[i];
            }
        }

        // 计算桶的数量
        int bucketCount = (maxValue - minValue) / bucketSize + 1;
        List<ArrayList<Integer>> buckets = new ArrayList<>(bucketCount);

        // 初始化桶
        for (int i = 0; i < bucketCount; i++) {
            buckets.add(new ArrayList<>());
        }

        // 将元素分配到桶中
        for (int i = 0; i < arr.length; i++) {
            int bucketIndex = (arr[i] - minValue) / bucketSize;
            buckets.get(bucketIndex).add(arr[i]);
        }

        // 对每个桶进行排序，可更换为效率高的排序算法
        for (int i = 0; i < bucketCount; i++) {
            Collections.sort(buckets.get(i));
        }

        // 将排序后的元素从桶中取出放入原数组
        int index = 0;
        for (ArrayList<Integer> bucket : buckets) {
            for (int value : bucket) {
                arr[index++] = value;
            }
        }
    }
}
